package com.zds.leetcode;

import java.util.LinkedList;
import java.util.List;

public class q_77 {

    public static void main(String[] args) {
        q_77 q_77 = new q_77();
        List<List<Integer>> combine = q_77.combine(4, 2);
        System.out.println(combine);
    }

    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtrack(n, k, 1);
        return res;
    }

    void backtrack(int end, int size, int now) {
        // 返回叶子节点
        if (track.size()==size){
            // 避免全局变量的污染
            res.add(new LinkedList<>(track));
            return;
        }

        for (int i=now;i<=end;i++) {
            // 做选择
            track.add(i);
            // 递归
            backtrack(end, size, i+1);
            // 撤销选择
            track.removeLast();
        }
    }
}
